1. Field of the Invention
The present invention generally relates to halftoning techniques in printers and, more particularly, to a method and apparatus for halftoning which construct and utilize a mask in a dithering algorithm for a multitone printer.
2. Background Description
Most printers today can print in only a limited number of colors. Digital halftoning is a technique for printing a picture (or more generally displaying it on some two-dimensional medium) using small dots with a limited number of colors such that it appears to consist of many colors when viewed from a proper distance. For example, a picture of black and white dots can appear to display grey colors when viewed from some distance.
The fastest and most commonly used methods for digital halftoning are dithering algorithms which use threshold arrays, also called dither matrices or dither masks. Masks can be constructed to generate dispersed dots, which means in particular that black dots can only cluster if the grey level is dark enough to make it improbable or impossible to have all black dots isolated. As a consequence, they are not practical for most laser printers or xerographic printers, since these types of printers have problems printing isolated dots.
To achieve clustering, one can use a traditional threshold array constructed so that increasing the grey level corresponds to printing larger and larger clusters at a fixed periodicity. This method does not produce unpleasant artifacts. However, depending on the printer resolution and the periodicity chosen, either the number of grey levels that can be represented using such a method is too small or the clusters which are generated are too large. To correct these effects, one usually uses a multicell array, which includes several single-cluster threshold arrays. In a multicell array, several clusters are grown with the same spatial period as in the single-cluster array, but are not grown simultaneously with each other. This allows for additional intermediate grey levels. U.S. patent application Ser. No. 08/909,535 filed on Aug. 12, 1997, by Gerhard Thompson, Charles Tresser and Chai Wah Wu for xe2x80x9cMulticell Clustered Mask with Blue Noise Adjustmentsxe2x80x9d and U.S. patent application Ser. No. 08/943,881 filed on Oct. 13, 1997, by Gerhard Thompson, Charles Tresser and Chai Wah Wu for xe2x80x9cClustered Aperiodic Maskxe2x80x9d , now U.S. Pat. No. 5,917,951, are examples of multicell-type approaches to obtain masks with many grey levels.
Better quality is expected if instead of black and white, one can print dots with several grey intensities. Usually the number of grey levels available, including white and black, is a power of two. The power can then be understood as the number of bits containing the grey level, and one speaks of multibit printing. This restriction to a power of two is not necessary and we will use the term multitone in the general case. It is in fact convenient to consider simple black and white (one bit) as a special case of multitone for the rest of the discussion.
Once a mask is devised for halftoning grey scale pictures, prior art allows it to be used for color pictures. The individual color planes are halftoned using rotated periodic masks, in order to avoid moirxc3xa9 patterns, or other changes are made to aperiodic masks such as described for instance in U.S. Pat. No. 5,341,228 to K. J. Parker and T. Mitsa in the case of a blue noise mask.
Most of these techniques and others are reviewed in the book Digital Halftoning, MIT Press, Cambridge, Mass. (1987) by R. Ulichney, which is a general reference for digital halftoning.
When printing a grey area which corresponds to one of the printable dot intensities, common sense would a priori suggest that the most reasonable way to do so is by printing dots with the given intensity. There are two issues associated with this approach. The first is that the resulting grey may be darker than the individual grey dot in cases where the printed dots are not perfectly square and overlap. This however can be corrected by calibration. The other problem is that if the printer is a laser printer, or uses some other technology which cannot consistently control the intensity of each dot, some unpleasant patterning may be generated when trying to print large patches of intermediate grey levels. Several proprietary methods have been proposed to solve this problem which work reasonably well with some printers.
It is therefore an object of the present invention to provide a technique which allows one to solve the above problems so that enough parameters are available to adjust so as to adapt the method to any multitone printer, and any cell size.
According to the invention, a method and apparatus are provided for the halftoning of grey scale (or components of color) images using a multitone printer. Digital halftoning techniques in printers which construct and utilize a mask in a dithering algorithm for a multitone printer are generalized by using a decision matrix in conjunction with the dithering matrix. In the practice of the method, a pixel grey value and a mask threshold value are obtained for each pixel in the image. Based on these values, a decision is made on the grey level to be printed at each pixel. The apparatus for halftoning of a grey scale image using a multitone printer according to the invention comprises an image storage for storing an image and means, such as a scanner, for inputting an image in the image storage. A dither matrix stores mask threshold values. A pixel grey value and a mask threshold value for each pixel in an image stored in said image storage are obtained, and a decision on the grey level to be printed at each pixel depending on the input grey value and the mask threshold value. For extensions to multiple component color images, each component is treated independently as if it were a grey scale image. The mask threshold values and sizes are, in that case, likely to be tuned per component and therefore different.